/*
 * @Author: liusheng
 * @Date: 2022-07-25 20:38:04
 * @LastEditors: liusheng
 * @LastEditTime: 2022-07-25 20:38:07
 * @Description: 剑指 Offer II 101. 分割等和子集
 * email:liusheng613@126.com
 * Copyright (c) 2022 by liusheng/liusheng, All Rights Reserved. 
 * 
 剑指 Offer II 101. 分割等和子集
给定一个非空的正整数数组 nums ，请判断能否将这些数字分成元素和相等的两部分。

 

示例 1：

输入：nums = [1,5,11,5]
输出：true
解释：nums 可以分割成 [1, 5, 5] 和 [11] 。
示例 2：

输入：nums = [1,2,3,5]
输出：false
解释：nums 不可以分为和相等的两部分
 

提示：

1 <= nums.length <= 200
1 <= nums[i] <= 100
 

注意：本题与主站 416 题相同： https://leetcode-cn.com/problems/partition-equal-subset-sum/

通过次数14,614  提交次数29,102
 */

#include "header.h"

class Solution {
public:
    /*
    scroll array optmize。
    */
    bool canPartition(vector<int>& nums) {
        int n = nums.size();

        int sum = 0;
        int maxNum = 0;
        for (auto num : nums)
        {
            sum += num;
            if (num > maxNum)
            {
                maxNum = num;
            }
        }

        if (sum % 2)
        {
            return false;
        }

        int target = sum / 2;
        if (maxNum > target)
        {
            return false;
        }

        //dp[i][j],from index 0 - i find target j
        //so dp[i][0] = true

        //find target
        vector<bool> dp(target + 1,false);
        vector<bool> predp = dp;
        dp[0] = true;

        for (int i = 1; i < n; ++i)
        {
            predp = dp;
            int num = nums[i];
            //np problem
            for (int j = 1; j <= target; ++j)
            {
                if (j >= num)
                {
                    //dp[i-1][j-num] select num
                    //dp[i-1][j] not select num
                    dp[j] = predp[j-num] | predp[j];
                }
                else
                {
                    dp[j] = predp[j];
                }
            }
        }

        return dp[target];
    }
};